home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / snobol4 / misc.lha / compress.bdl next >
Text File  |  1993-07-24  |  59KB  |  2,124 lines
  1. # To unbundle, sh this file
  2. echo unbundling Makefile 1>&2
  3. cat >Makefile <<'AlBeRtEiNsTeIn'
  4. #
  5. #    @(#)Makefile    5.5 (Berkeley) 9/18/85
  6. #
  7. COMFLAGS=-DBSD4_2 -O -DSACREDMEM=256000
  8. BIN=${DESTDIR}/usr/ucb
  9.  
  10. compress: compress.c USERMEM
  11.     cc $(COMFLAGS) -DUSERMEM=`cat USERMEM` -o compress compress.c
  12.  
  13. # USERMEM may have to be set by hand.  It should contain the amount of
  14. # available user memory in bytes.  Set it to zero, for physical memory
  15. # less than 1 Meg.
  16. USERMEM:
  17.     sh usermem.sh > USERMEM
  18.  
  19. install: compress
  20.     install -s compress $(BIN)
  21.     rm -f $(BIN)/uncompress $(BIN)/zcat
  22.     ln $(BIN)/compress $(BIN)/uncompress
  23.     ln $(BIN)/compress $(BIN)/zcat
  24.  
  25. # Temporarily don't delete USERMEM.  When chroot'ed to /nbsd, usermem.sh
  26. # fails totally.
  27. clean:
  28.     rm -f compress core errs
  29. #    rm -f compress USERMEM core errs
  30. AlBeRtEiNsTeIn
  31. echo unbundling README 1>&2
  32. cat >README <<'AlBeRtEiNsTeIn'
  33.  
  34.     @(#)README    5.3 (Berkeley) 9/17/85
  35.  
  36. Compress version 4.0 improvements over 3.0:
  37.     o compress() speedup (10-50%) by changing division hash to xor
  38.     o decompress() speedup (5-10%)
  39.     o Memory requirements reduced (3-30%)
  40.     o Stack requirements reduced to less than 4kb
  41.     o Removed 'Big+Fast' compress code (FBITS) because of compress speedup
  42.         o Portability mods for Z8000 and PC/XT (but not zeus 3.2)
  43.     o Default to 'quiet' mode
  44.     o Unification of 'force' flags
  45.     o Manual page overhaul
  46.     o Portability enhancement for M_XENIX
  47.     o Removed text on #else and #endif
  48.     o Added "-V" switch to print version and options
  49.     o Added #defines for SIGNED_COMPARE_SLOW
  50.     o Added Makefile and "usermem" program
  51.     o Removed all floating point computations
  52.     o New programs: [deleted]
  53.  
  54. The "usermem" script attempts to determine the maximum process size.  Some
  55. editing of the script may be necessary (see the comments).  [It should work
  56. fine on 4.3 bsd.] If you can't get it to work at all, just create file
  57. "USERMEM" containing the maximum process size in decimal.
  58.  
  59. The following preprocessor symbols control the compilation of "compress.c":
  60.  
  61.     o USERMEM        Maximum process memory on the system
  62.     o SACREDMEM        Amount to reserve for other proceses
  63.     o SIGNED_COMPARE_SLOW    Unsigned compare instructions are faster
  64.     o NO_UCHAR        Don't use "unsigned char" types
  65.     o BITS            Overrules default set by USERMEM-SACREDMEM
  66.     o vax            Generate inline assembler
  67.     o interdata        Defines SIGNED_COMPARE_SLOW
  68.     o M_XENIX        Makes arrays < 65536 bytes each
  69.     o pdp11            BITS=12, NO_UCHAR
  70.     o z8000            BITS=12
  71.     o pcxt            BITS=12
  72.     o BSD4_2        Allow long filenames ( > 14 characters) &
  73.                 Call setlinebuf(stderr)
  74.  
  75. The difference "usermem-sacredmem" determines the maximum BITS that can be
  76. specified with the "-b" flag.
  77.  
  78. memory: at least        BITS
  79. ------  -- -----                ----
  80.      433,484             16
  81.      229,600             15
  82.      127,536             14
  83.       73,464             13
  84.            0             12
  85.  
  86. The default is BITS=16.
  87.  
  88. The maximum bits can be overrulled by specifying "-DBITS=bits" at
  89. compilation time.
  90.  
  91. WARNING: files compressed on a large machine with more bits than allowed by 
  92. a version of compress on a smaller machine cannot be decompressed!  Use the
  93. "-b12" flag to generate a file on a large machine that can be uncompressed 
  94. on a 16-bit machine.
  95.  
  96. The output of compress 4.0 is fully compatible with that of compress 3.0.
  97. In other words, the output of compress 4.0 may be fed into uncompress 3.0 or
  98. the output of compress 3.0 may be fed into uncompress 4.0.
  99.  
  100. The output of compress 4.0 not compatible with that of
  101. compress 2.0.  However, compress 4.0 still accepts the output of
  102. compress 2.0.  To generate output that is compatible with compress
  103. 2.0, use the undocumented "-C" flag.
  104.  
  105.     -from mod.sources, submitted by vax135!petsd!joe (Joe Orost), 8/1/85
  106. --------------------------------
  107.  
  108. Enclosed is compress version 3.0 with the following changes:
  109.  
  110. 1.    "Block" compression is performed.  After the BITS run out, the
  111.     compression ratio is checked every so often.  If it is decreasing,
  112.     the table is cleared and a new set of substrings are generated.
  113.  
  114.     This makes the output of compress 3.0 not compatible with that of
  115.     compress 2.0.  However, compress 3.0 still accepts the output of
  116.     compress 2.0.  To generate output that is compatible with compress
  117.     2.0, use the undocumented "-C" flag.
  118.  
  119. 2.    A quiet "-q" flag has been added for use by the news system.
  120.  
  121. 3.    The character chaining has been deleted and the program now uses
  122.     hashing.  This improves the speed of the program, especially
  123.     during decompression.  Other speed improvements have been made,
  124.     such as using putc() instead of fwrite().
  125.  
  126. 4.    A large table is used on large machines when a relatively small
  127.     number of bits is specified.  This saves much time when compressing
  128.     for a 16-bit machine on a 32-bit virtual machine.  Note that the
  129.     speed improvement only occurs when the input file is > 30000
  130.     characters, and the -b BITS is less than or equal to the cutoff
  131.     described below.
  132.  
  133. Most of these changes were made by James A. Woods (ames!jaw).  Thank you
  134. James!
  135.  
  136. To compile compress:
  137.  
  138.     cc -O -DUSERMEM=usermem -o compress compress.c
  139.  
  140. Where "usermem" is the amount of physical user memory available (in bytes).  
  141. If any physical memory is to be reserved for other processes, put in 
  142. "-DSACREDMEM sacredmem", where "sacredmem" is the amount to be reserved.
  143.  
  144. The difference "usermem-sacredmem" determines the maximum BITS that can be
  145. specified, and the cutoff bits where the large+fast table is used.
  146.  
  147. memory: at least        BITS        cutoff
  148. ------  -- -----                ----            ------
  149.    4,718,592              16          13
  150.    2,621,440              16          12
  151.    1,572,864             16          11
  152.    1,048,576             16          10
  153.      631,808             16               --
  154.      329,728             15               --
  155.      178,176             14          --
  156.       99,328             13          --
  157.            0             12          --
  158.  
  159. The default memory size is 750,000 which gives a maximum BITS=16 and no
  160. large+fast table.
  161.  
  162. The maximum bits can be overruled by specifying "-DBITS=bits" at
  163. compilation time.
  164.  
  165. If your machine doesn't support unsigned characters, define "NO_UCHAR" 
  166. when compiling.
  167.  
  168. If your machine has "int" as 16-bits, define "SHORT_INT" when compiling.
  169.  
  170. After compilation, move "compress" to a standard executable location, such 
  171. as /usr/local.  Then:
  172.     cd /usr/local
  173.     ln compress uncompress
  174.     ln compress zcat
  175.  
  176. On machines that have a fixed stack size (such as Perkin-Elmer), set the
  177. stack to at least 12kb.  ("setstack compress 12" on Perkin-Elmer).
  178.  
  179. Next, install the manual (compress.l).
  180.     cp compress.l /usr/man/manl
  181.     cd /usr/man/manl
  182.     ln compress.l uncompress.l
  183.     ln compress.l zcat.l
  184.  
  185.         - or -
  186.  
  187.     cp compress.l /usr/man/man1/compress.1
  188.     cd /usr/man/man1
  189.     ln compress.1 uncompress.1
  190.     ln compress.1 zcat.1
  191.  
  192.                     regards,
  193.                     petsd!joe
  194.  
  195. Here is a note from the net:
  196.  
  197. >From hplabs!pesnta!amd!turtlevax!ken Sat Jan  5 03:35:20 1985
  198. Path: ames!hplabs!pesnta!amd!turtlevax!ken
  199. From: ken@turtlevax.UUCP (Ken Turkowski)
  200. Newsgroups: net.sources
  201. Subject: Re: Compress release 3.0 : sample Makefile
  202. Organization: CADLINC, Inc. @ Menlo Park, CA
  203.  
  204. In the compress 3.0 source recently posted to mod.sources, there is a
  205. #define variable which can be set for optimum performance on a machine
  206. with a large amount of memory.  A program (usermem) to calculate the
  207. useable amount of physical user memory is enclosed, as well as a sample
  208. 4.2bsd Vax Makefile for compress.
  209.  
  210. Here is the README file from the previous version of compress (2.0):
  211.  
  212. >Enclosed is compress.c version 2.0 with the following bugs fixed:
  213. >
  214. >1.    The packed files produced by compress are different on different
  215. >    machines and dependent on the vax sysgen option.
  216. >        The bug was in the different byte/bit ordering on the
  217. >        various machines.  This has been fixed.
  218. >
  219. >        This version is NOT compatible with the original vax posting
  220. >        unless the '-DCOMPATIBLE' option is specified to the C
  221. >        compiler.  The original posting has a bug which I fixed, 
  222. >        causing incompatible files.  I recommend you NOT to use this
  223. >        option unless you already have a lot of packed files from
  224. >        the original posting by thomas.
  225. >2.    The exit status is not well defined (on some machines) causing the
  226. >    scripts to fail.
  227. >        The exit status is now 0,1 or 2 and is documented in
  228. >        compress.l.
  229. >3.    The function getopt() is not available in all C libraries.
  230. >        The function getopt() is no longer referenced by the
  231. >        program.
  232. >4.    Error status is not being checked on the fwrite() and fflush() calls.
  233. >        Fixed.
  234. >
  235. >The following enhancements have been made:
  236. >
  237. >1.    Added facilities of "compact" into the compress program.  "Pack",
  238. >    "Unpack", and "Pcat" are no longer required (no longer supplied).
  239. >2.    Installed work around for C compiler bug with "-O".
  240. >3.    Added a magic number header (\037\235).  Put the bits specified
  241. >    in the file.
  242. >4.    Added "-f" flag to force overwrite of output file.
  243. >5.    Added "-c" flag and "zcat" program.  'ln compress zcat' after you
  244. >    compile.
  245. >6.    The 'uncompress' script has been deleted; simply 
  246. >    'ln compress uncompress' after you compile and it will work.
  247. >7.    Removed extra bit masking for machines that support unsigned
  248. >    characters.  If your machine doesn't support unsigned characters,
  249. >    define "NO_UCHAR" when compiling.
  250. >
  251. >Compile "compress.c" with "-O -o compress" flags.  Move "compress" to a
  252. >standard executable location, such as /usr/local.  Then:
  253. >    cd /usr/local
  254. >    ln compress uncompress
  255. >    ln compress zcat
  256. >
  257. >On machines that have a fixed stack size (such as Perkin-Elmer), set the
  258. >stack to at least 12kb.  ("setstack compress 12" on Perkin-Elmer).
  259. >
  260. >Next, install the manual (compress.l).
  261. >    cp compress.l /usr/man/manl        - or -
  262. >    cp compress.l /usr/man/man1/compress.1
  263. >
  264. >Here is the README that I sent with my first posting:
  265. >
  266. >>Enclosed is a modified version of compress.c, along with scripts to make it
  267. >>run identically to pack(1), unpack(1), an pcat(1).  Here is what I
  268. >>(petsd!joe) and a colleague (petsd!peora!srd) did:
  269. >>
  270. >>1. Removed VAX dependencies.
  271. >>2. Changed the struct to separate arrays; saves mucho memory.
  272. >>3. Did comparisons in unsigned, where possible.  (Faster on Perkin-Elmer.)
  273. >>4. Sorted the character next chain and changed the search to stop
  274. >>prematurely.  This saves a lot on the execution time when compressing.
  275. >>
  276. >>This version is totally compatible with the original version.  Even though
  277. >>lint(1) -p has no complaints about compress.c, it won't run on a 16-bit
  278. >>machine, due to the size of the arrays.
  279. >>
  280. >>Here is the README file from the original author:
  281. >> 
  282. >>>Well, with all this discussion about file compression (for news batching
  283. >>>in particular) going around, I decided to implement the text compression
  284. >>>algorithm described in the June Computer magazine.  The author claimed
  285. >>>blinding speed and good compression ratios.  It's certainly faster than
  286. >>>compact (but, then, what wouldn't be), but it's also the same speed as
  287. >>>pack, and gets better compression than both of them.  On 350K bytes of
  288. >>>unix-wizards, compact took about 8 minutes of CPU, pack took about 80
  289. >>>seconds, and compress (herein) also took 80 seconds.  But, compact and
  290. >>>pack got about 30% compression, whereas compress got over 50%.  So, I
  291. >>>decided I had something, and that others might be interested, too.
  292. >>>
  293. >>>As is probably true of compact and pack (although I haven't checked),
  294. >>>the byte order within a word is probably relevant here, but as long as
  295. >>>you stay on a single machine type, you should be ok.  (Can anybody
  296. >>>elucidate on this?)  There are a couple of asm's in the code (extv and
  297. >>>insv instructions), so anyone porting it to another machine will have to
  298. >>>deal with this anyway (and could probably make it compatible with Vax
  299. >>>byte order at the same time).  Anyway, I've linted the code (both with
  300. >>>and without -p), so it should run elsewhere.  Note the longs in the
  301. >>>code, you can take these out if you reduce BITS to <= 15.
  302. >>>
  303. >>>Have fun, and as always, if you make good enhancements, or bug fixes,
  304. >>>I'd like to see them.
  305. >>>
  306. >>>=Spencer (thomas@utah-20, {harpo,hplabs,arizona}!utah-cs!thomas)
  307. >>
  308. >>                    regards,
  309. >>                    joe
  310. >>
  311. >>--
  312. >>Full-Name:  Joseph M. Orost
  313. >>UUCP:       ..!{decvax,ucbvax,ihnp4}!vax135!petsd!joe
  314. >>US Mail:    MS 313; Perkin-Elmer; 106 Apple St; Tinton Falls, NJ 07724
  315. >>Phone:      (201) 870-5844
  316. AlBeRtEiNsTeIn
  317. echo unbundling USERMEM 1>&2
  318. cat >USERMEM <<'AlBeRtEiNsTeIn'
  319. 1170000
  320. AlBeRtEiNsTeIn
  321. echo unbundling compress.1 1>&2
  322. cat >compress.1 <<'AlBeRtEiNsTeIn'
  323. .\"    @(#)compress.1    6.3 (Berkeley) 9/17/85
  324. .\"
  325. .TH COMPRESS 1 "September 17, 1985"
  326. .UC 6
  327. .SH NAME
  328. compress, uncompress, zcat \- compress and expand data
  329. .PU
  330. .SH SYNOPSIS
  331. .ll +8
  332. .B compress
  333. [
  334. .B \-f
  335. ] [
  336. .B \-v
  337. ] [
  338. .B \-c
  339. ] [
  340. .B \-b
  341. .I bits
  342. ] [
  343. .I "name \&..."
  344. ]
  345. .ll -8
  346. .br
  347. .B uncompress
  348. [
  349. .B \-f
  350. ] [
  351. .B \-v
  352. ] [
  353. .B \-c
  354. ] [
  355. .I "name \&..."
  356. ]
  357. .br
  358. .B zcat
  359. [
  360. .I "name \&..."
  361. ]
  362. .SH DESCRIPTION
  363. .I Compress
  364. reduces the size of the named files using adaptive Lempel-Ziv coding.
  365. Whenever possible,
  366. each file is replaced by one with the extension
  367. .B "\&.Z,"
  368. while keeping the same ownership modes, access and modification times.
  369. If no files are specified, the standard input is compressed to the
  370. standard output.
  371. Compressed files can be restored to their original form using
  372. .I uncompress
  373. or
  374. .I zcat.
  375. .PP
  376. The
  377. .B \-f
  378. option will force compression of
  379. .I name.
  380. This is useful for compressing an entire directory,
  381. even if some of the files do not actually shrink.
  382. If
  383. .B \-f
  384. is not given and
  385. .I compress
  386. is run in the foreground,
  387. the user is prompted as to whether an existing file should be overwritten.
  388. .PP
  389. The
  390. .B \-c
  391. (``cat'') option makes
  392. .I compress/uncompress
  393. write to the standard output; no files are changed.
  394. The nondestructive behavior of
  395. .I zcat
  396. is identical to that of
  397. .I uncompress
  398. .B \-c.
  399. .PP
  400. .I Compress
  401. uses the modified Lempel-Ziv algorithm popularized in
  402. "A Technique for High Performance Data Compression",
  403. Terry A. Welch,
  404. .I "IEEE Computer,"
  405. vol. 17, no. 6 (June 1984), pp. 8-19.
  406. Common substrings in the file are first replaced by 9-bit codes 257 and up.
  407. When code 512 is reached, the algorithm switches to 10-bit codes and
  408. continues to use more bits until the
  409. limit specified by the
  410. .B \-b
  411. flag is reached (default 16).
  412. .I Bits
  413. must be between 9 and 16.  The default can be changed in the source to allow
  414. .I compress
  415. to be run on a smaller machine.
  416. .PP
  417. After the
  418. .I bits
  419. limit is attained,
  420. .I compress
  421. periodically checks the compression ratio.  If it is increasing,
  422. .I compress
  423. continues to use the existing code dictionary.  However,
  424. if the compression ratio decreases,
  425. .I compress
  426. discards the table of substrings and rebuilds it from scratch.  This allows
  427. the algorithm to adapt to the next "block" of the file.
  428. .PP
  429. Note that the
  430. .B \-b
  431. flag is omitted for
  432. .I uncompress,
  433. since the 
  434. .I bits
  435. parameter specified during compression
  436. is encoded within the output, along with
  437. a magic number to ensure that neither decompression of random data nor
  438. recompression of compressed data is attempted. 
  439. .PP
  440. .ne 8
  441. The amount of compression obtained depends on the size of the
  442. input, the number of
  443. .I bits
  444. per code, and the distribution of common substrings.
  445. Typically, text such as source code or English
  446. is reduced by 50\-60%.
  447. Compression is generally much better than that achieved by
  448. Huffman coding (as used in
  449. .IR pack ),
  450. or adaptive Huffman coding
  451. .RI ( compact ),
  452. and takes less time to compute.
  453. .PP
  454. Under the
  455. .B \-v
  456. option,
  457. a message is printed yielding the percentage of
  458. reduction for each file compressed.
  459. .PP
  460. Exit status is normally 0;
  461. if the last file is larger after (attempted) compression, the status is 2;
  462. if an error occurs, exit status is 1.
  463. .SH "DIAGNOSTICS"
  464. Usage: compress [\-fvc] [\-b maxbits] [file ...]
  465. .in +8
  466. Invalid options were specified on the command line.
  467. .in -8
  468. Missing maxbits
  469. .in +8
  470. Maxbits must follow
  471. .BR \-b \.
  472. .in -8
  473. .IR file :
  474. not in compressed format
  475. .in +8
  476. The file specified to
  477. .I uncompress
  478. has not been compressed.
  479. .in -8
  480. .IR file :
  481. compressed with 
  482. .I xx
  483. bits, can only handle 
  484. .I yy
  485. bits
  486. .in +8
  487. .I File
  488. was compressed by a program that could deal with
  489. more 
  490. .I bits
  491. than the compress code on this machine.
  492. Recompress the file with smaller
  493. .IR bits \.
  494. .in -8
  495. .IR file :
  496. already has .Z suffix -- no change
  497. .in +8
  498. The file is assumed to be already compressed.
  499. Rename the file and try again.
  500. .in -8
  501. .IR file :
  502. filename too long to tack on .Z
  503. .in +8
  504. The file cannot be compressed because its name is longer than
  505. 12 characters.
  506. Rename and try again.
  507. This message does not occur on BSD systems.
  508. .in -8
  509. .I file
  510. already exists; do you wish to overwrite (y or n)?
  511. .in +8
  512. Respond "y" if you want the output file to be replaced; "n" if not.
  513. .in -8
  514. uncompress: corrupt input
  515. .in +8
  516. A SIGSEGV violation was detected which usually means that the input file is
  517. corrupted.
  518. .in -8
  519. Compression: 
  520. .I "xx.xx%"
  521. .in +8
  522. Percentage of the input saved by compression.
  523. (Relevant only for
  524. .BR \-v \.)
  525. .in -8
  526. -- not a regular file: unchanged
  527. .in +8
  528. When the input file is not a regular file,
  529. (e.g. a directory), it is
  530. left unaltered.
  531. .in -8
  532. -- has 
  533. .I xx 
  534. other links: unchanged
  535. .in +8
  536. The input file has links; it is left unchanged.  See
  537. .IR ln "(1)"
  538. for more information.
  539. .in -8
  540. -- file unchanged
  541. .in +8
  542. No savings is achieved by
  543. compression.  The input remains virgin.
  544. .in -8
  545. .SH "BUGS"
  546. Although compressed files are compatible between machines with large memory,
  547. .BR \-b \12
  548. should be used for file transfer to architectures with 
  549. a small process data space (64KB or less, as exhibited by the DEC PDP
  550. series, the Intel 80286, etc.)
  551. AlBeRtEiNsTeIn
  552. echo unbundling compress.c 1>&2
  553. cat >compress.c <<'AlBeRtEiNsTeIn'
  554. #ifndef lint
  555. static char sccsid[] = "@(#)compress.c    5.7 (Berkeley) 9/17/85";
  556. #endif not lint
  557.  
  558. /* 
  559.  * Compress - data compression program 
  560.  */
  561. #define    min(a,b)    ((a>b) ? b : a)
  562.  
  563. /*
  564.  * machine variants which require cc -Dmachine:  pdp11, z8000, pcxt
  565.  */
  566.  
  567. /*
  568.  * Set USERMEM to the maximum amount of physical user memory available
  569.  * in bytes.  USERMEM is used to determine the maximum BITS that can be used
  570.  * for compression.
  571.  *
  572.  * SACREDMEM is the amount of physical memory saved for others; compress
  573.  * will hog the rest.
  574.  */
  575. #ifndef SACREDMEM
  576. #define SACREDMEM    0
  577. #endif
  578.  
  579. #ifndef USERMEM
  580. # define USERMEM     450000    /* default user memory */
  581. #endif
  582.  
  583. #ifdef interdata        /* (Perkin-Elmer) */
  584. #define SIGNED_COMPARE_SLOW    /* signed compare is slower than unsigned */
  585. #endif
  586.  
  587. #ifdef pdp11
  588. # define BITS     12    /* max bits/code for 16-bit machine */
  589. # define NO_UCHAR    /* also if "unsigned char" functions as signed char */
  590. # undef USERMEM 
  591. #endif /* pdp11 */    /* don't forget to compile with -i */
  592.  
  593. #ifdef z8000
  594. # define BITS     12
  595. # undef vax        /* weird preprocessor */
  596. # undef USERMEM 
  597. #endif /* z8000 */
  598.  
  599. #ifdef pcxt
  600. # define BITS   12
  601. # undef USERMEM
  602. #endif /* pcxt */
  603.  
  604. #ifdef USERMEM
  605. # if USERMEM >= (433484+SACREDMEM)
  606. #  define PBITS    16
  607. # else
  608. #  if USERMEM >= (229600+SACREDMEM)
  609. #   define PBITS    15
  610. #  else
  611. #   if USERMEM >= (127536+SACREDMEM)
  612. #    define PBITS    14
  613. #   else
  614. #    if USERMEM >= (73464+SACREDMEM)
  615. #     define PBITS    13
  616. #    else
  617. #     define PBITS    12
  618. #    endif
  619. #   endif
  620. #  endif
  621. # endif
  622. # undef USERMEM
  623. #endif /* USERMEM */
  624.  
  625. #ifdef PBITS        /* Preferred BITS for this memory size */
  626. # ifndef BITS
  627. #  define BITS PBITS
  628. # endif BITS
  629. #endif /* PBITS */
  630.  
  631. #if BITS == 16
  632. # define HSIZE    69001        /* 95% occupancy */
  633. #endif
  634. #if BITS == 15
  635. # define HSIZE    35023        /* 94% occupancy */
  636. #endif
  637. #if BITS == 14
  638. # define HSIZE    18013        /* 91% occupancy */
  639. #endif
  640. #if BITS == 13
  641. # define HSIZE    9001        /* 91% occupancy */
  642. #endif
  643. #if BITS <= 12
  644. # define HSIZE    5003        /* 80% occupancy */
  645. #endif
  646.  
  647. #ifdef M_XENIX            /* Stupid compiler can't handle arrays with */
  648. # if BITS == 16            /* more than 65535 bytes - so we fake it */
  649. #  define XENIX_16
  650. # else
  651. #  if BITS > 13            /* Code only handles BITS = 12, 13, or 16 */
  652. #   define BITS    13
  653. #  endif
  654. # endif
  655. #endif
  656.  
  657. /*
  658.  * a code_int must be able to hold 2**BITS values of type int, and also -1
  659.  */
  660. #if BITS > 15
  661. typedef long int    code_int;
  662. #else
  663. typedef int        code_int;
  664. #endif
  665.  
  666. #ifdef SIGNED_COMPARE_SLOW
  667. typedef unsigned long int count_int;
  668. typedef unsigned short int count_short;
  669. #else
  670. typedef long int      count_int;
  671. #endif
  672.  
  673. #ifdef NO_UCHAR
  674.  typedef char    char_type;
  675. #else
  676.  typedef    unsigned char    char_type;
  677. #endif /* UCHAR */
  678. char_type magic_header[] = { "\037\235" };    /* 1F 9D */
  679.  
  680. /* Defines for third byte of header */
  681. #define BIT_MASK    0x1f
  682. #define BLOCK_MASK    0x80
  683. /* Masks 0x40 and 0x20 are free.  I think 0x20 should mean that there is
  684.    a fourth header byte (for expansion).
  685. */
  686. #define INIT_BITS 9            /* initial number of bits/code */
  687.  
  688. /*
  689.  * compress.c - File compression ala IEEE Computer, June 1984.
  690.  *
  691.  * Authors:    Spencer W. Thomas    (decvax!harpo!utah-cs!utah-gr!thomas)
  692.  *        Jim McKie        (decvax!mcvax!jim)
  693.  *        Steve Davies        (decvax!vax135!petsd!peora!srd)
  694.  *        Ken Turkowski        (decvax!decwrl!turtlevax!ken)
  695.  *        James A. Woods        (decvax!ihnp4!ames!jaw)
  696.  *        Joe Orost        (decvax!vax135!petsd!joe)
  697.  *
  698.  * $Header: compress.c,v 4.0 85/07/30 12:50:00 joe Release $
  699.  * $Log:    compress.c,v $
  700.  * Revision 4.0  85/07/30  12:50:00  joe
  701.  * Removed ferror() calls in output routine on every output except first.
  702.  * Prepared for release to the world.
  703.  * 
  704.  * Revision 3.6  85/07/04  01:22:21  joe
  705.  * Remove much wasted storage by overlaying hash table with the tables
  706.  * used by decompress: tab_suffix[1<<BITS], stack[8000].  Updated USERMEM
  707.  * computations.  Fixed dump_tab() DEBUG routine.
  708.  *
  709.  * Revision 3.5  85/06/30  20:47:21  jaw
  710.  * Change hash function to use exclusive-or.  Rip out hash cache.  These
  711.  * speedups render the megamemory version defunct, for now.  Make decoder
  712.  * stack global.  Parts of the RCS trunks 2.7, 2.6, and 2.1 no longer apply.
  713.  *
  714.  * Revision 3.4  85/06/27  12:00:00  ken
  715.  * Get rid of all floating-point calculations by doing all compression ratio
  716.  * calculations in fixed point.
  717.  *
  718.  * Revision 3.3  85/06/24  21:53:24  joe
  719.  * Incorporate portability suggestion for M_XENIX.  Got rid of text on #else
  720.  * and #endif lines.  Cleaned up #ifdefs for vax and interdata.
  721.  *
  722.  * Revision 3.2  85/06/06  21:53:24  jaw
  723.  * Incorporate portability suggestions for Z8000, IBM PC/XT from mailing list.
  724.  * Default to "quiet" output (no compression statistics).
  725.  *
  726.  * Revision 3.1  85/05/12  18:56:13  jaw
  727.  * Integrate decompress() stack speedups (from early pointer mods by McKie).
  728.  * Repair multi-file USERMEM gaffe.  Unify 'force' flags to mimic semantics
  729.  * of SVR2 'pack'.  Streamline block-compress table clear logic.  Increase 
  730.  * output byte count by magic number size.
  731.  * 
  732.  * Revision 3.0   84/11/27  11:50:00  petsd!joe
  733.  * Set HSIZE depending on BITS.  Set BITS depending on USERMEM.  Unrolled
  734.  * loops in clear routines.  Added "-C" flag for 2.0 compatibility.  Used
  735.  * unsigned compares on Perkin-Elmer.  Fixed foreground check.
  736.  *
  737.  * Revision 2.7   84/11/16  19:35:39  ames!jaw
  738.  * Cache common hash codes based on input statistics; this improves
  739.  * performance for low-density raster images.  Pass on #ifdef bundle
  740.  * from Turkowski.
  741.  *
  742.  * Revision 2.6   84/11/05  19:18:21  ames!jaw
  743.  * Vary size of hash tables to reduce time for small files.
  744.  * Tune PDP-11 hash function.
  745.  *
  746.  * Revision 2.5   84/10/30  20:15:14  ames!jaw
  747.  * Junk chaining; replace with the simpler (and, on the VAX, faster)
  748.  * double hashing, discussed within.  Make block compression standard.
  749.  *
  750.  * Revision 2.4   84/10/16  11:11:11  ames!jaw
  751.  * Introduce adaptive reset for block compression, to boost the rate
  752.  * another several percent.  (See mailing list notes.)
  753.  *
  754.  * Revision 2.3   84/09/22  22:00:00  petsd!joe
  755.  * Implemented "-B" block compress.  Implemented REVERSE sorting of tab_next.
  756.  * Bug fix for last bits.  Changed fwrite to putchar loop everywhere.
  757.  *
  758.  * Revision 2.2   84/09/18  14:12:21  ames!jaw
  759.  * Fold in news changes, small machine typedef from thomas,
  760.  * #ifdef interdata from joe.
  761.  *
  762.  * Revision 2.1   84/09/10  12:34:56  ames!jaw
  763.  * Configured fast table lookup for 32-bit machines.
  764.  * This cuts user time in half for b <= FBITS, and is useful for news batching
  765.  * from VAX to PDP sites.  Also sped up decompress() [fwrite->putc] and
  766.  * added signal catcher [plus beef in writeerr()] to delete effluvia.
  767.  *
  768.  * Revision 2.0   84/08/28  22:00:00  petsd!joe
  769.  * Add check for foreground before prompting user.  Insert maxbits into
  770.  * compressed file.  Force file being uncompressed to end with ".Z".
  771.  * Added "-c" flag and "zcat".  Prepared for release.
  772.  *
  773.  * Revision 1.10  84/08/24  18:28:00  turtlevax!ken
  774.  * Will only compress regular files (no directories), added a magic number
  775.  * header (plus an undocumented -n flag to handle old files without headers),
  776.  * added -f flag to force overwriting of possibly existing destination file,
  777.  * otherwise the user is prompted for a response.  Will tack on a .Z to a
  778.  * filename if it doesn't have one when decompressing.  Will only replace
  779.  * file if it was compressed.
  780.  *
  781.  * Revision 1.9  84/08/16  17:28:00  turtlevax!ken
  782.  * Removed scanargs(), getopt(), added .Z extension and unlimited number of
  783.  * filenames to compress.  Flags may be clustered (-Ddvb12) or separated
  784.  * (-D -d -v -b 12), or combination thereof.  Modes and other status is
  785.  * copied with copystat().  -O bug for 4.2 seems to have disappeared with
  786.  * 1.8.
  787.  *
  788.  * Revision 1.8  84/08/09  23:15:00  joe
  789.  * Made it compatible with vax version, installed jim's fixes/enhancements
  790.  *
  791.  * Revision 1.6  84/08/01  22:08:00  joe
  792.  * Sped up algorithm significantly by sorting the compress chain.
  793.  *
  794.  * Revision 1.5  84/07/13  13:11:00  srd
  795.  * Added C version of vax asm routines.  Changed structure to arrays to
  796.  * save much memory.  Do unsigned compares where possible (faster on
  797.  * Perkin-Elmer)
  798.  *
  799.  * Revision 1.4  84/07/05  03:11:11  thomas
  800.  * Clean up the code a little and lint it.  (Lint complains about all
  801.  * the regs used in the asm, but I'm not going to "fix" this.)
  802.  *
  803.  * Revision 1.3  84/07/05  02:06:54  thomas
  804.  * Minor fixes.
  805.  *
  806.  * Revision 1.2  84/07/05  00:27:27  thomas
  807.  * Add variable bit length output.
  808.  *
  809.  */
  810. static char rcs_ident[] = "$Header: compress.c,v 4.0 85/07/30 12:50:00 joe Release $";
  811.  
  812. #include <stdio.h>
  813. #include <ctype.h>
  814. #include <signal.h>
  815. #include <sys/types.h>
  816. #include <sys/stat.h>
  817.  
  818. #define ARGVAL() (*++(*argv) || (--argc && *++argv))
  819.  
  820. int n_bits;                /* number of bits/code */
  821. int maxbits = BITS;            /* user settable max # bits/code */
  822. code_int maxcode;            /* maximum code, given n_bits */
  823. code_int maxmaxcode = 1 << BITS;    /* should NEVER generate this code */
  824. #ifdef COMPATIBLE        /* But wrong! */
  825. # define MAXCODE(n_bits)    (1 << (n_bits) - 1)
  826. #else
  827. # define MAXCODE(n_bits)    ((1 << (n_bits)) - 1)
  828. #endif /* COMPATIBLE */
  829.  
  830. #ifdef XENIX_16
  831. count_int htab0[8192];
  832. count_int htab1[8192];
  833. count_int htab2[8192];
  834. count_int htab3[8192];
  835. count_int htab4[8192];
  836. count_int htab5[8192];
  837. count_int htab6[8192];
  838. count_int htab7[8192];
  839. count_int htab8[HSIZE-65536];
  840. count_int * htab[9] = {
  841.     htab0, htab1, htab2, htab3, htab4, htab5, htab6, htab7, htab8 };
  842.  
  843. #define htabof(i)    (htab[(i) >> 13][(i) & 0x1fff])
  844. unsigned short code0tab[16384];
  845. unsigned short code1tab[16384];
  846. unsigned short code2tab[16384];
  847. unsigned short code3tab[16384];
  848. unsigned short code4tab[16384];
  849. unsigned short * codetab[5] = {
  850.     code0tab, code1tab, code2tab, code3tab, code4tab };
  851.  
  852. #define codetabof(i)    (codetab[(i) >> 14][(i) & 0x3fff])
  853.  
  854. #else    /* Normal machine */
  855. count_int htab [HSIZE];
  856. unsigned short codetab [HSIZE];
  857. #define htabof(i)    htab[i]
  858. #define codetabof(i)    codetab[i]
  859. #endif    /* XENIX_16 */
  860. code_int hsize = HSIZE;            /* for dynamic table sizing */
  861. count_int fsize;
  862.  
  863. /*
  864.  * To save much memory, we overlay the table used by compress() with those
  865.  * used by decompress().  The tab_prefix table is the same size and type
  866.  * as the codetab.  The tab_suffix table needs 2**BITS characters.  We
  867.  * get this from the beginning of htab.  The output stack uses the rest
  868.  * of htab, and contains characters.  There is plenty of room for any
  869.  * possible stack (stack used to be 8000 characters).
  870.  */
  871.  
  872. #define tab_prefixof(i)    codetabof(i)
  873. #ifdef XENIX_16
  874. # define tab_suffixof(i)    ((char_type *)htab[(i)>>15])[(i) & 0x7fff]
  875. # define de_stack        ((char_type *)(htab2))
  876. #else    /* Normal machine */
  877. # define tab_suffixof(i)    ((char_type *)(htab))[i]
  878. # define de_stack        ((char_type *)&tab_suffixof(1<<BITS))
  879. #endif    /* XENIX_16 */
  880.  
  881. code_int free_ent = 0;            /* first unused entry */
  882. int exit_stat = 0;
  883.  
  884. code_int getcode();
  885.  
  886. Usage() {
  887. #ifdef DEBUG
  888. fprintf(stderr,"Usage: compress [-dDVfc] [-b maxbits] [file ...]\n");
  889. }
  890. int debug = 0;
  891. #else
  892. fprintf(stderr,"Usage: compress [-fvc] [-b maxbits] [file ...]\n");
  893. }
  894. #endif /* DEBUG */
  895. int nomagic = 0;    /* Use a 3-byte magic number header, unless old file */
  896. int zcat_flg = 0;    /* Write output on stdout, suppress messages */
  897. int quiet = 1;        /* don't tell me about compression */
  898.  
  899. /*
  900.  * block compression parameters -- after all codes are used up,
  901.  * and compression rate changes, start over.
  902.  */
  903. int block_compress = BLOCK_MASK;
  904. int clear_flg = 0;
  905. long int ratio = 0;
  906. #define CHECK_GAP 10000    /* ratio check interval */
  907. count_int checkpoint = CHECK_GAP;
  908. /*
  909.  * the next two codes should not be changed lightly, as they must not
  910.  * lie within the contiguous general code space.
  911.  */ 
  912. #define FIRST    257    /* first free entry */
  913. #define    CLEAR    256    /* table clear output code */
  914.  
  915. int force = 0;
  916. char ofname [100];
  917. #ifdef DEBUG
  918. int verbose = 0;
  919. #endif /* DEBUG */
  920. int (*bgnd_flag)();
  921.  
  922. int do_decomp = 0;
  923.  
  924. /*****************************************************************
  925.  * TAG( main )
  926.  *
  927.  * Algorithm from "A Technique for High Performance Data Compression",
  928.  * Terry A. Welch, IEEE Computer Vol 17, No 6 (June 1984), pp 8-19.
  929.  *
  930.  * Usage: compress [-dfvc] [-b bits] [file ...]
  931.  * Inputs:
  932.  *    -d:        If given, decompression is done instead.
  933.  *
  934.  *      -c:         Write output on stdout, don't remove original.
  935.  *
  936.  *      -b:         Parameter limits the max number of bits/code.
  937.  *
  938.  *    -f:        Forces output file to be generated, even if one already
  939.  *            exists, and even if no space is saved by compressing.
  940.  *            If -f is not used, the user will be prompted if stdin is
  941.  *            a tty, otherwise, the output file will not be overwritten.
  942.  *
  943.  *      -v:        Write compression statistics
  944.  *
  945.  *     file ...:   Files to be compressed.  If none specified, stdin
  946.  *            is used.
  947.  * Outputs:
  948.  *    file.Z:        Compressed form of file with same mode, owner, and utimes
  949.  *     or stdout   (if stdin used as input)
  950.  *
  951.  * Assumptions:
  952.  *    When filenames are given, replaces with the compressed version
  953.  *    (.Z suffix) only if the file decreases in size.
  954.  * Algorithm:
  955.  *     Modified Lempel-Ziv method (LZW).  Basically finds common
  956.  * substrings and replaces them with a variable size code.  This is
  957.  * deterministic, and can be done on the fly.  Thus, the decompression
  958.  * procedure needs no input table, but tracks the way the table was built.
  959.  */
  960.  
  961. main( argc, argv )
  962. register int argc; char **argv;
  963. {
  964.     int overwrite = 0;    /* Do not overwrite unless given -f flag */
  965.     char tempname[100];
  966.     char **filelist, **fileptr;
  967.     char *cp, *rindex(), *malloc();
  968.     struct stat statbuf;
  969.     extern onintr(), oops();
  970.  
  971.  
  972.     if ( (bgnd_flag = signal ( SIGINT, SIG_IGN )) != SIG_IGN ) {
  973.     signal ( SIGINT, onintr );
  974.     signal ( SIGSEGV, oops );
  975.     }
  976.  
  977. #ifdef COMPATIBLE
  978.     nomagic = 1;    /* Original didn't have a magic number */
  979. #endif /* COMPATIBLE */
  980.  
  981.     filelist = fileptr = (char **)(malloc(argc * sizeof(*argv)));
  982.     *filelist = NULL;
  983.  
  984.     if((cp = rindex(argv[0], '/')) != 0) {
  985.     cp++;
  986.     } else {
  987.     cp = argv[0];
  988.     }
  989.     if(strcmp(cp, "uncompress") == 0) {
  990.     do_decomp = 1;
  991.     } else if(strcmp(cp, "zcat") == 0) {
  992.     do_decomp = 1;
  993.     zcat_flg = 1;
  994.     }
  995.  
  996. #ifdef BSD4_2
  997.     /* 4.2BSD dependent - take it out if not */
  998.     setlinebuf( stderr );
  999. #endif /* BSD4_2 */
  1000.  
  1001.     /* Argument Processing
  1002.      * All flags are optional.
  1003.      * -D => debug
  1004.      * -V => print Version; debug verbose
  1005.      * -d => do_decomp
  1006.      * -v => unquiet
  1007.      * -f => force overwrite of output file
  1008.      * -n => no header: useful to uncompress old files
  1009.      * -b maxbits => maxbits.  If -b is specified, then maxbits MUST be
  1010.      *        given also.
  1011.      * -c => cat all output to stdout
  1012.      * -C => generate output compatible with compress 2.0.
  1013.      * if a string is left, must be an input filename.
  1014.      */
  1015.     for (argc--, argv++; argc > 0; argc--, argv++) {
  1016.     if (**argv == '-') {    /* A flag argument */
  1017.         while (*++(*argv)) {    /* Process all flags in this arg */
  1018.         switch (**argv) {
  1019. #ifdef DEBUG
  1020.             case 'D':
  1021.             debug = 1;
  1022.             break;
  1023.             case 'V':
  1024.             verbose = 1;
  1025.             version();
  1026.             break;
  1027. #else
  1028.             case 'V':
  1029.             version();
  1030.             break;
  1031. #endif /* DEBUG */
  1032.             case 'v':
  1033.             quiet = 0;
  1034.             break;
  1035.             case 'd':
  1036.             do_decomp = 1;
  1037.             break;
  1038.             case 'f':
  1039.             case 'F':
  1040.             overwrite = 1;
  1041.             force = 1;
  1042.             break;
  1043.             case 'n':
  1044.             nomagic = 1;
  1045.             break;
  1046.             case 'C':
  1047.             block_compress = 0;
  1048.             break;
  1049.             case 'b':
  1050.             if (!ARGVAL()) {
  1051.                 fprintf(stderr, "Missing maxbits\n");
  1052.                 Usage();
  1053.                 exit(1);
  1054.             }
  1055.             maxbits = atoi(*argv);
  1056.             goto nextarg;
  1057.             case 'c':
  1058.             zcat_flg = 1;
  1059.             break;
  1060.             case 'q':
  1061.             quiet = 1;
  1062.             break;
  1063.             default:
  1064.             fprintf(stderr, "Unknown flag: '%c'; ", **argv);
  1065.             Usage();
  1066.             exit(1);
  1067.         }
  1068.         }
  1069.     }
  1070.     else {        /* Input file name */
  1071.         *fileptr++ = *argv;    /* Build input file list */
  1072.         *fileptr = NULL;
  1073.         /* process nextarg; */
  1074.     }
  1075.     nextarg: continue;
  1076.     }
  1077.  
  1078.     if(maxbits < INIT_BITS) maxbits = INIT_BITS;
  1079.     if (maxbits > BITS) maxbits = BITS;
  1080.     maxmaxcode = 1 << maxbits;
  1081.  
  1082.     if (*filelist != NULL) {
  1083.     for (fileptr = filelist; *fileptr; fileptr++) {
  1084.         exit_stat = 0;
  1085.         if (do_decomp != 0) {            /* DECOMPRESSION */
  1086.         /* Check for .Z suffix */
  1087.         if (strcmp(*fileptr + strlen(*fileptr) - 2, ".Z") != 0) {
  1088.             /* No .Z: tack one on */
  1089.             strcpy(tempname, *fileptr);
  1090.             strcat(tempname, ".Z");
  1091.             *fileptr = tempname;
  1092.         }
  1093.         /* Open input file */
  1094.         if ((freopen(*fileptr, "r", stdin)) == NULL) {
  1095.             perror(*fileptr); continue;
  1096.         }
  1097.         /* Check the magic number */
  1098.         if (nomagic == 0) {
  1099.             if ((getchar() != (magic_header[0] & 0xFF))
  1100.              || (getchar() != (magic_header[1] & 0xFF))) {
  1101.             fprintf(stderr, "%s: not in compressed format\n",
  1102.                 *fileptr);
  1103.             continue;
  1104.             }
  1105.             maxbits = getchar();    /* set -b from file */
  1106.             block_compress = maxbits & BLOCK_MASK;
  1107.             maxbits &= BIT_MASK;
  1108.             maxmaxcode = 1 << maxbits;
  1109.             if(maxbits > BITS) {
  1110.             fprintf(stderr,
  1111.             "%s: compressed with %d bits, can only handle %d bits\n",
  1112.             *fileptr, maxbits, BITS);
  1113.             continue;
  1114.             }
  1115.         }
  1116.         /* Generate output filename */
  1117.         strcpy(ofname, *fileptr);
  1118.         ofname[strlen(*fileptr) - 2] = '\0';  /* Strip off .Z */
  1119.         } else {                    /* COMPRESSION */
  1120.         if (strcmp(*fileptr + strlen(*fileptr) - 2, ".Z") == 0) {
  1121.                 fprintf(stderr, "%s: already has .Z suffix -- no change\n",
  1122.                 *fileptr);
  1123.             continue;
  1124.         }
  1125.         /* Open input file */
  1126.         if ((freopen(*fileptr, "r", stdin)) == NULL) {
  1127.             perror(*fileptr); continue;
  1128.         }
  1129.         stat ( *fileptr, &statbuf );
  1130.         fsize = (long) statbuf.st_size;
  1131.         /*
  1132.          * tune hash table size for small files -- ad hoc,
  1133.          * but the sizes match earlier #defines, which
  1134.          * serve as upper bounds on the number of output codes. 
  1135.          */
  1136.         hsize = HSIZE;
  1137.         if ( fsize < (1 << 12) )
  1138.             hsize = min ( 5003, HSIZE );
  1139.         else if ( fsize < (1 << 13) )
  1140.             hsize = min ( 9001, HSIZE );
  1141.         else if ( fsize < (1 << 14) )
  1142.             hsize = min ( 18013, HSIZE );
  1143.         else if ( fsize < (1 << 15) )
  1144.             hsize = min ( 35023, HSIZE );
  1145.         else if ( fsize < 47000 )
  1146.             hsize = min ( 50021, HSIZE );
  1147.  
  1148.         /* Generate output filename */
  1149.         strcpy(ofname, *fileptr);
  1150. #ifndef BSD4_2        /* Short filenames */
  1151.         if ((cp=rindex(ofname,'/')) != NULL)    cp++;
  1152.         else                    cp = ofname;
  1153.         if (strlen(cp) > 12) {
  1154.             fprintf(stderr,"%s: filename too long to tack on .Z\n",cp);
  1155.             continue;
  1156.         }
  1157. #endif  /* BSD4_2        Long filenames allowed */
  1158.         strcat(ofname, ".Z");
  1159.         }
  1160.         /* Check for overwrite of existing file */
  1161.         if (overwrite == 0 && zcat_flg == 0) {
  1162.         if (stat(ofname, &statbuf) == 0) {
  1163.             char response[2];
  1164.             response[0] = 'n';
  1165.             fprintf(stderr, "%s already exists;", ofname);
  1166.             if (foreground()) {
  1167.             fprintf(stderr, " do you wish to overwrite %s (y or n)? ",
  1168.             ofname);
  1169.             fflush(stderr);
  1170.             read(2, response, 2);
  1171.             while (response[1] != '\n') {
  1172.                 if (read(2, response+1, 1) < 0) {    /* Ack! */
  1173.                 perror("stderr"); break;
  1174.                 }
  1175.             }
  1176.             }
  1177.             if (response[0] != 'y') {
  1178.             fprintf(stderr, "\tnot overwritten\n");
  1179.             continue;
  1180.             }
  1181.         }
  1182.         }
  1183.         if(zcat_flg == 0) {        /* Open output file */
  1184.         if (freopen(ofname, "w", stdout) == NULL) {
  1185.             perror(ofname);
  1186.             continue;
  1187.         }
  1188.         if(!quiet)
  1189.             fprintf(stderr, "%s: ", *fileptr);
  1190.         }
  1191.  
  1192.         /* Actually do the compression/decompression */
  1193.         if (do_decomp == 0)    compress();
  1194. #ifndef DEBUG
  1195.         else            decompress();
  1196. #else
  1197.         else if (debug == 0)    decompress();
  1198.         else            printcodes();
  1199.         if (verbose)        dump_tab();
  1200. #endif /* DEBUG */
  1201.         if(zcat_flg == 0) {
  1202.         copystat(*fileptr, ofname);    /* Copy stats */
  1203.         if((exit_stat == 1) || (!quiet))
  1204.             putc('\n', stderr);
  1205.         }
  1206.     }
  1207.     } else {        /* Standard input */
  1208.     if (do_decomp == 0) {
  1209.         compress();
  1210. #ifdef DEBUG
  1211.         if(verbose)        dump_tab();
  1212. #endif /* DEBUG */
  1213.         if(!quiet)
  1214.             putc('\n', stderr);
  1215.     } else {
  1216.         /* Check the magic number */
  1217.         if (nomagic == 0) {
  1218.         if ((getchar()!=(magic_header[0] & 0xFF))
  1219.          || (getchar()!=(magic_header[1] & 0xFF))) {
  1220.             fprintf(stderr, "stdin: not in compressed format\n");
  1221.             exit(1);
  1222.         }
  1223.         maxbits = getchar();    /* set -b from file */
  1224.         block_compress = maxbits & BLOCK_MASK;
  1225.         maxbits &= BIT_MASK;
  1226.         maxmaxcode = 1 << maxbits;
  1227.         fsize = 100000;        /* assume stdin large for USERMEM */
  1228.         if(maxbits > BITS) {
  1229.             fprintf(stderr,
  1230.             "stdin: compressed with %d bits, can only handle %d bits\n",
  1231.             maxbits, BITS);
  1232.             exit(1);
  1233.         }
  1234.         }
  1235. #ifndef DEBUG
  1236.         decompress();
  1237. #else
  1238.         if (debug == 0)    decompress();
  1239.         else        printcodes();
  1240.         if (verbose)    dump_tab();
  1241. #endif /* DEBUG */
  1242.     }
  1243.     }
  1244.     exit(exit_stat);
  1245. }
  1246.  
  1247. static int offset;
  1248. long int in_count = 1;            /* length of input */
  1249. long int bytes_out;            /* length of compressed output */
  1250. long int out_count = 0;            /* # of codes output (for debugging) */
  1251.  
  1252. /*
  1253.  * compress stdin to stdout
  1254.  *
  1255.  * Algorithm:  use open addressing double hashing (no chaining) on the 
  1256.  * prefix code / next character combination.  We do a variant of Knuth's
  1257.  * algorithm D (vol. 3, sec. 6.4) along with G. Knott's relatively-prime
  1258.  * secondary probe.  Here, the modular division first probe is gives way
  1259.  * to a faster exclusive-or manipulation.  Also do block compression with
  1260.  * an adaptive reset, whereby the code table is cleared when the compression
  1261.  * ratio decreases, but after the table fills.  The variable-length output
  1262.  * codes are re-sized at this point, and a special CLEAR code is generated
  1263.  * for the decompressor.  Late addition:  construct the table according to
  1264.  * file size for noticeable speed improvement on small files.  Please direct
  1265.  * questions about this implementation to ames!jaw.
  1266.  */
  1267.  
  1268. compress() {
  1269.     register long fcode;
  1270.     register code_int i = 0;
  1271.     register int c;
  1272.     register code_int ent;
  1273. #ifdef XENIX_16
  1274.     register code_int disp;
  1275. #else    /* Normal machine */
  1276.     register int disp;
  1277. #endif
  1278.     register code_int hsize_reg;
  1279.     register int hshift;
  1280.  
  1281. #ifndef COMPATIBLE
  1282.     if (nomagic == 0) {
  1283.     putchar(magic_header[0]); putchar(magic_header[1]);
  1284.     putchar((char)(maxbits | block_compress));
  1285.     if(ferror(stdout))
  1286.         writeerr();
  1287.     }
  1288. #endif /* COMPATIBLE */
  1289.  
  1290.     offset = 0;
  1291.     bytes_out = 3;        /* includes 3-byte header mojo */
  1292.     out_count = 0;
  1293.     clear_flg = 0;
  1294.     ratio = 0;
  1295.     in_count = 1;
  1296.     checkpoint = CHECK_GAP;
  1297.     maxcode = MAXCODE(n_bits = INIT_BITS);
  1298.     free_ent = ((block_compress) ? FIRST : 256 );
  1299.  
  1300.     ent = getchar ();
  1301.  
  1302.     hshift = 0;
  1303.     for ( fcode = (long) hsize;  fcode < 65536L; fcode *= 2L )
  1304.         hshift++;
  1305.     hshift = 8 - hshift;        /* set hash code range bound */
  1306.  
  1307.     hsize_reg = hsize;
  1308.     cl_hash( (count_int) hsize_reg);        /* clear hash table */
  1309.  
  1310. #ifdef SIGNED_COMPARE_SLOW
  1311.     while ( (c = getchar()) != (unsigned) EOF ) {
  1312. #else
  1313.     while ( (c = getchar()) != EOF ) {
  1314. #endif
  1315.     in_count++;
  1316.     fcode = (long) (((long) c << maxbits) + ent);
  1317.      i = ((c << hshift) ^ ent);    /* xor hashing */
  1318.  
  1319.     if ( htabof (i) == fcode ) {
  1320.         ent = codetabof (i);
  1321.         continue;
  1322.     } else if ( (long)htabof (i) < 0 )    /* empty slot */
  1323.         goto nomatch;
  1324.      disp = hsize_reg - i;        /* secondary hash (after G. Knott) */
  1325.     if ( i == 0 )
  1326.         disp = 1;
  1327. probe:
  1328.     if ( (i -= disp) < 0 )
  1329.         i += hsize_reg;
  1330.  
  1331.     if ( htabof (i) == fcode ) {
  1332.         ent = codetabof (i);
  1333.         continue;
  1334.     }
  1335.     if ( (long)htabof (i) > 0 ) 
  1336.         goto probe;
  1337. nomatch:
  1338.     output ( (code_int) ent );
  1339.     out_count++;
  1340.      ent = c;
  1341. #ifdef SIGNED_COMPARE_SLOW
  1342.     if ( (unsigned) free_ent < (unsigned) maxmaxcode) {
  1343. #else
  1344.     if ( free_ent < maxmaxcode ) {
  1345. #endif
  1346.          codetabof (i) = free_ent++;    /* code -> hashtable */
  1347.         htabof (i) = fcode;
  1348.     }
  1349.     else if ( (count_int)in_count >= checkpoint && block_compress )
  1350.         cl_block ();
  1351.     }
  1352.     /*
  1353.      * Put out the final code.
  1354.      */
  1355.     output( (code_int)ent );
  1356.     out_count++;
  1357.     output( (code_int)-1 );
  1358.  
  1359.     /*
  1360.      * Print out stats on stderr
  1361.      */
  1362.     if(zcat_flg == 0 && !quiet) {
  1363. #ifdef DEBUG
  1364.     fprintf( stderr,
  1365.         "%ld chars in, %ld codes (%ld bytes) out, compression factor: ",
  1366.         in_count, out_count, bytes_out );
  1367.     prratio( stderr, in_count, bytes_out );
  1368.     fprintf( stderr, "\n");
  1369.     fprintf( stderr, "\tCompression as in compact: " );
  1370.     prratio( stderr, in_count-bytes_out, in_count );
  1371.     fprintf( stderr, "\n");
  1372.     fprintf( stderr, "\tLargest code (of last block) was %d (%d bits)\n",
  1373.         free_ent - 1, n_bits );
  1374. #else /* !DEBUG */
  1375.     fprintf( stderr, "Compression: " );
  1376.     prratio( stderr, in_count-bytes_out, in_count );
  1377. #endif /* DEBUG */
  1378.     }
  1379.     if(bytes_out > in_count)    /* exit(2) if no savings */
  1380.     exit_stat = 2;
  1381.     return;
  1382. }
  1383.  
  1384. /*****************************************************************
  1385.  * TAG( output )
  1386.  *
  1387.  * Output the given code.
  1388.  * Inputs:
  1389.  *     code:    A n_bits-bit integer.  If == -1, then EOF.  This assumes
  1390.  *        that n_bits =< (long)wordsize - 1.
  1391.  * Outputs:
  1392.  *     Outputs code to the file.
  1393.  * Assumptions:
  1394.  *    Chars are 8 bits long.
  1395.  * Algorithm:
  1396.  *     Maintain a BITS character long buffer (so that 8 codes will
  1397.  * fit in it exactly).  Use the VAX insv instruction to insert each
  1398.  * code in turn.  When the buffer fills up empty it and start over.
  1399.  */
  1400.  
  1401. static char buf[BITS];
  1402.  
  1403. #ifndef vax
  1404. char_type lmask[9] = {0xff, 0xfe, 0xfc, 0xf8, 0xf0, 0xe0, 0xc0, 0x80, 0x00};
  1405. char_type rmask[9] = {0x00, 0x01, 0x03, 0x07, 0x0f, 0x1f, 0x3f, 0x7f, 0xff};
  1406. #endif /* vax */
  1407.  
  1408. output( code )
  1409. code_int  code;
  1410. {
  1411. #ifdef DEBUG
  1412.     static int col = 0;
  1413. #endif /* DEBUG */
  1414.  
  1415.     /*
  1416.      * On the VAX, it is important to have the register declarations
  1417.      * in exactly the order given, or the asm will break.
  1418.      */
  1419.     register int r_off = offset, bits= n_bits;
  1420.     register char * bp = buf;
  1421.  
  1422. #ifdef DEBUG
  1423.     if ( verbose )
  1424.         fprintf( stderr, "%5d%c", code,
  1425.             (col+=6) >= 74 ? (col = 0, '\n') : ' ' );
  1426. #endif /* DEBUG */
  1427.     if ( code >= 0 ) {
  1428. #ifdef vax
  1429.     /* VAX DEPENDENT!! Implementation on other machines is below.
  1430.      *
  1431.      * Translation: Insert BITS bits from the argument starting at
  1432.      * offset bits from the beginning of buf.
  1433.      */
  1434.     0;    /* Work around for pcc -O bug with asm and if stmt */
  1435.     asm( "insv    4(ap),r11,r10,(r9)" );
  1436. #else /* not a vax */
  1437. /* 
  1438.  * byte/bit numbering on the VAX is simulated by the following code
  1439.  */
  1440.     /*
  1441.      * Get to the first byte.
  1442.      */
  1443.     bp += (r_off >> 3);
  1444.     r_off &= 7;
  1445.     /*
  1446.      * Since code is always >= 8 bits, only need to mask the first
  1447.      * hunk on the left.
  1448.      */
  1449.     *bp = (*bp & rmask[r_off]) | (code << r_off) & lmask[r_off];
  1450.     bp++;
  1451.     bits -= (8 - r_off);
  1452.     code >>= 8 - r_off;
  1453.     /* Get any 8 bit parts in the middle (<=1 for up to 16 bits). */
  1454.     if ( bits >= 8 ) {
  1455.         *bp++ = code;
  1456.         code >>= 8;
  1457.         bits -= 8;
  1458.     }
  1459.     /* Last bits. */
  1460.     if(bits)
  1461.         *bp = code;
  1462. #endif /* vax */
  1463.     offset += n_bits;
  1464.     if ( offset == (n_bits << 3) ) {
  1465.         bp = buf;
  1466.         bits = n_bits;
  1467.         bytes_out += bits;
  1468.         do
  1469.         putchar(*bp++);
  1470.         while(--bits);
  1471.         offset = 0;
  1472.     }
  1473.  
  1474.     /*
  1475.      * If the next entry is going to be too big for the code size,
  1476.      * then increase it, if possible.
  1477.      */
  1478.     if ( free_ent > maxcode || (clear_flg > 0))
  1479.     {
  1480.         /*
  1481.          * Write the whole buffer, because the input side won't
  1482.          * discover the size increase until after it has read it.
  1483.          */
  1484.         if ( offset > 0 ) {
  1485.         if( fwrite( buf, 1, n_bits, stdout ) != n_bits)
  1486.             writeerr();
  1487.         bytes_out += n_bits;
  1488.         }
  1489.         offset = 0;
  1490.  
  1491.         if ( clear_flg ) {
  1492.                 maxcode = MAXCODE (n_bits = INIT_BITS);
  1493.             clear_flg = 0;
  1494.         }
  1495.         else {
  1496.             n_bits++;
  1497.             if ( n_bits == maxbits )
  1498.             maxcode = maxmaxcode;
  1499.             else
  1500.             maxcode = MAXCODE(n_bits);
  1501.         }
  1502. #ifdef DEBUG
  1503.         if ( debug ) {
  1504.         fprintf( stderr, "\nChange to %d bits\n", n_bits );
  1505.         col = 0;
  1506.         }
  1507. #endif /* DEBUG */
  1508.     }
  1509.     } else {
  1510.     /*
  1511.      * At EOF, write the rest of the buffer.
  1512.      */
  1513.     if ( offset > 0 )
  1514.         fwrite( buf, 1, (offset + 7) / 8, stdout );
  1515.     bytes_out += (offset + 7) / 8;
  1516.     offset = 0;
  1517.     fflush( stdout );
  1518. #ifdef DEBUG
  1519.     if ( verbose )
  1520.         fprintf( stderr, "\n" );
  1521. #endif /* DEBUG */
  1522.     if( ferror( stdout ) )
  1523.         writeerr();
  1524.     }
  1525. }
  1526.  
  1527. /*
  1528.  * Decompress stdin to stdout.  This routine adapts to the codes in the
  1529.  * file building the "string" table on-the-fly; requiring no table to
  1530.  * be stored in the compressed file.  The tables used herein are shared
  1531.  * with those of the compress() routine.  See the definitions above.
  1532.  */
  1533.  
  1534. decompress() {
  1535.     register char_type *stackp;
  1536.     register int finchar;
  1537.     register code_int code, oldcode, incode;
  1538.  
  1539.     /*
  1540.      * As above, initialize the first 256 entries in the table.
  1541.      */
  1542.     maxcode = MAXCODE(n_bits = INIT_BITS);
  1543.     for ( code = 255; code >= 0; code-- ) {
  1544.     tab_prefixof(code) = 0;
  1545.     tab_suffixof(code) = (char_type)code;
  1546.     }
  1547.     free_ent = ((block_compress) ? FIRST : 256 );
  1548.  
  1549.     finchar = oldcode = getcode();
  1550.     if(oldcode == -1)    /* EOF already? */
  1551.     return;            /* Get out of here */
  1552.     putchar( (char)finchar );        /* first code must be 8 bits = char */
  1553.     if(ferror(stdout))        /* Crash if can't write */
  1554.     writeerr();
  1555.     stackp = de_stack;
  1556.  
  1557.     while ( (code = getcode()) > -1 ) {
  1558.  
  1559.     if ( (code == CLEAR) && block_compress ) {
  1560.         for ( code = 255; code >= 0; code-- )
  1561.         tab_prefixof(code) = 0;
  1562.         clear_flg = 1;
  1563.         free_ent = FIRST - 1;
  1564.         if ( (code = getcode ()) == -1 )    /* O, untimely death! */
  1565.         break;
  1566.     }
  1567.     incode = code;
  1568.     /*
  1569.      * Special case for KwKwK string.
  1570.      */
  1571.     if ( code >= free_ent ) {
  1572.             *stackp++ = finchar;
  1573.         code = oldcode;
  1574.     }
  1575.  
  1576.     /*
  1577.      * Generate output characters in reverse order
  1578.      */
  1579. #ifdef SIGNED_COMPARE_SLOW
  1580.     while ( ((unsigned long)code) >= ((unsigned long)256) ) {
  1581. #else
  1582.     while ( code >= 256 ) {
  1583. #endif
  1584.         *stackp++ = tab_suffixof(code);
  1585.         code = tab_prefixof(code);
  1586.     }
  1587.     *stackp++ = finchar = tab_suffixof(code);
  1588.  
  1589.     /*
  1590.      * And put them out in forward order
  1591.      */
  1592.     do
  1593.         putchar ( *--stackp );
  1594.     while ( stackp > de_stack );
  1595.  
  1596.     /*
  1597.      * Generate the new entry.
  1598.      */
  1599.     if ( (code=free_ent) < maxmaxcode ) {
  1600.         tab_prefixof(code) = (unsigned short)oldcode;
  1601.         tab_suffixof(code) = finchar;
  1602.         free_ent = code+1;
  1603.     } 
  1604.     /*
  1605.      * Remember previous code.
  1606.      */
  1607.     oldcode = incode;
  1608.     }
  1609.     fflush( stdout );
  1610.     if(ferror(stdout))
  1611.     writeerr();
  1612. }
  1613.  
  1614. /*****************************************************************
  1615.  * TAG( getcode )
  1616.  *
  1617.  * Read one code from the standard input.  If EOF, return -1.
  1618.  * Inputs:
  1619.  *     stdin
  1620.  * Outputs:
  1621.  *     code or -1 is returned.
  1622.  */
  1623.  
  1624. code_int
  1625. getcode() {
  1626.     /*
  1627.      * On the VAX, it is important to have the register declarations
  1628.      * in exactly the order given, or the asm will break.
  1629.      */
  1630.     register code_int code;
  1631.     static int offset = 0, size = 0;
  1632.     static char_type buf[BITS];
  1633.     register int r_off, bits;
  1634.     register char_type *bp = buf;
  1635.  
  1636.     if ( clear_flg > 0 || offset >= size || free_ent > maxcode ) {
  1637.     /*
  1638.      * If the next entry will be too big for the current code
  1639.      * size, then we must increase the size.  This implies reading
  1640.      * a new buffer full, too.
  1641.      */
  1642.     if ( free_ent > maxcode ) {
  1643.         n_bits++;
  1644.         if ( n_bits == maxbits )
  1645.         maxcode = maxmaxcode;    /* won't get any bigger now */
  1646.         else
  1647.         maxcode = MAXCODE(n_bits);
  1648.     }
  1649.     if ( clear_flg > 0) {
  1650.             maxcode = MAXCODE (n_bits = INIT_BITS);
  1651.         clear_flg = 0;
  1652.     }
  1653.     size = fread( buf, 1, n_bits, stdin );
  1654.     if ( size <= 0 )
  1655.         return -1;            /* end of file */
  1656.     offset = 0;
  1657.     /* Round size down to integral number of codes */
  1658.     size = (size << 3) - (n_bits - 1);
  1659.     }
  1660.     r_off = offset;
  1661.     bits = n_bits;
  1662. #ifdef vax
  1663.     asm( "extzv   r10,r9,(r8),r11" );
  1664. #else /* not a vax */
  1665.     /*
  1666.      * Get to the first byte.
  1667.      */
  1668.     bp += (r_off >> 3);
  1669.     r_off &= 7;
  1670.     /* Get first part (low order bits) */
  1671. #ifdef NO_UCHAR
  1672.     code = ((*bp++ >> r_off) & rmask[8 - r_off]) & 0xff;
  1673. #else
  1674.     code = (*bp++ >> r_off);
  1675. #endif /* NO_UCHAR */
  1676.     bits -= (8 - r_off);
  1677.     r_off = 8 - r_off;        /* now, offset into code word */
  1678.     /* Get any 8 bit parts in the middle (<=1 for up to 16 bits). */
  1679.     if ( bits >= 8 ) {
  1680. #ifdef NO_UCHAR
  1681.         code |= (*bp++ & 0xff) << r_off;
  1682. #else
  1683.         code |= *bp++ << r_off;
  1684. #endif /* NO_UCHAR */
  1685.         r_off += 8;
  1686.         bits -= 8;
  1687.     }
  1688.     /* high order bits. */
  1689.     code |= (*bp & rmask[bits]) << r_off;
  1690. #endif /* vax */
  1691.     offset += n_bits;
  1692.  
  1693.     return code;
  1694. }
  1695.  
  1696. char *
  1697. rindex(s, c)        /* For those who don't have it in libc.a */
  1698. register char *s, c;
  1699. {
  1700.     char *p;
  1701.     for (p = NULL; *s; s++)
  1702.         if (*s == c)
  1703.         p = s;
  1704.     return(p);
  1705. }
  1706.  
  1707. #ifdef DEBUG
  1708. printcodes()
  1709. {
  1710.     /*
  1711.      * Just print out codes from input file.  For debugging.
  1712.      */
  1713.     code_int code;
  1714.     int col = 0, bits;
  1715.  
  1716.     bits = n_bits = INIT_BITS;
  1717.     maxcode = MAXCODE(n_bits);
  1718.     free_ent = ((block_compress) ? FIRST : 256 );
  1719.     while ( ( code = getcode() ) >= 0 ) {
  1720.     if ( (code == CLEAR) && block_compress ) {
  1721.            free_ent = FIRST - 1;
  1722.            clear_flg = 1;
  1723.     }
  1724.     else if ( free_ent < maxmaxcode )
  1725.         free_ent++;
  1726.     if ( bits != n_bits ) {
  1727.         fprintf(stderr, "\nChange to %d bits\n", n_bits );
  1728.         bits = n_bits;
  1729.         col = 0;
  1730.     }
  1731.     fprintf(stderr, "%5d%c", code, (col+=6) >= 74 ? (col = 0, '\n') : ' ' );
  1732.     }
  1733.     putc( '\n', stderr );
  1734.     exit( 0 );
  1735. }
  1736.  
  1737. code_int sorttab[1<<BITS];    /* sorted pointers into htab */
  1738.  
  1739. dump_tab()    /* dump string table */
  1740. {
  1741.     register int i, first;
  1742.     register ent;
  1743. #define STACK_SIZE    15000
  1744.     int stack_top = STACK_SIZE;
  1745.     register c;
  1746.  
  1747.     if(do_decomp == 0) {    /* compressing */
  1748.     register int flag = 1;
  1749.  
  1750.     for(i=0; i<hsize; i++) {    /* build sort pointers */
  1751.         if((long)htabof(i) >= 0) {
  1752.             sorttab[codetabof(i)] = i;
  1753.         }
  1754.     }
  1755.     first = block_compress ? FIRST : 256;
  1756.     for(i = first; i < free_ent; i++) {
  1757.         fprintf(stderr, "%5d: \"", i);
  1758.         de_stack[--stack_top] = '\n';
  1759.         de_stack[--stack_top] = '"';
  1760.         stack_top = in_stack((htabof(sorttab[i])>>maxbits)&0xff, 
  1761.                                      stack_top);
  1762.         for(ent=htabof(sorttab[i]) & ((1<<maxbits)-1);
  1763.             ent > 256;
  1764.             ent=htabof(sorttab[ent]) & ((1<<maxbits)-1)) {
  1765.             stack_top = in_stack(htabof(sorttab[ent]) >> maxbits,
  1766.                         stack_top);
  1767.         }
  1768.         stack_top = in_stack(ent, stack_top);
  1769.         fwrite( &de_stack[stack_top], 1, STACK_SIZE-stack_top, stderr);
  1770.            stack_top = STACK_SIZE;
  1771.     }
  1772.    } else if(!debug) {    /* decompressing */
  1773.  
  1774.        for ( i = 0; i < free_ent; i++ ) {
  1775.        ent = i;
  1776.        c = tab_suffixof(ent);
  1777.        if ( isascii(c) && isprint(c) )
  1778.            fprintf( stderr, "%5d: %5d/'%c'  \"",
  1779.                ent, tab_prefixof(ent), c );
  1780.        else
  1781.            fprintf( stderr, "%5d: %5d/\\%03o \"",
  1782.                ent, tab_prefixof(ent), c );
  1783.        de_stack[--stack_top] = '\n';
  1784.        de_stack[--stack_top] = '"';
  1785.        for ( ; ent != NULL;
  1786.            ent = (ent >= FIRST ? tab_prefixof(ent) : NULL) ) {
  1787.            stack_top = in_stack(tab_suffixof(ent), stack_top);
  1788.        }
  1789.        fwrite( &de_stack[stack_top], 1, STACK_SIZE - stack_top, stderr );
  1790.        stack_top = STACK_SIZE;
  1791.        }
  1792.     }
  1793. }
  1794.  
  1795. int
  1796. in_stack(c, stack_top)
  1797.     register c, stack_top;
  1798. {
  1799.     if ( (isascii(c) && isprint(c) && c != '\\') || c == ' ' ) {
  1800.         de_stack[--stack_top] = c;
  1801.     } else {
  1802.         switch( c ) {
  1803.         case '\n': de_stack[--stack_top] = 'n'; break;
  1804.         case '\t': de_stack[--stack_top] = 't'; break;
  1805.         case '\b': de_stack[--stack_top] = 'b'; break;
  1806.         case '\f': de_stack[--stack_top] = 'f'; break;
  1807.         case '\r': de_stack[--stack_top] = 'r'; break;
  1808.         case '\\': de_stack[--stack_top] = '\\'; break;
  1809.         default:
  1810.          de_stack[--stack_top] = '0' + c % 8;
  1811.          de_stack[--stack_top] = '0' + (c / 8) % 8;
  1812.          de_stack[--stack_top] = '0' + c / 64;
  1813.          break;
  1814.         }
  1815.         de_stack[--stack_top] = '\\';
  1816.     }
  1817.     return stack_top;
  1818. }
  1819. #endif /* DEBUG */
  1820.  
  1821. writeerr()
  1822. {
  1823.     perror ( ofname );
  1824.     unlink ( ofname );
  1825.     exit ( 1 );
  1826. }
  1827.  
  1828. copystat(ifname, ofname)
  1829. char *ifname, *ofname;
  1830. {
  1831.     struct stat statbuf;
  1832.     int mode;
  1833.     time_t timep[2];
  1834.  
  1835.     fclose(stdout);
  1836.     if (stat(ifname, &statbuf)) {        /* Get stat on input file */
  1837.     perror(ifname);
  1838.     return;
  1839.     }
  1840.     if ((statbuf.st_mode & S_IFMT/*0170000*/) != S_IFREG/*0100000*/) {
  1841.     if(quiet)
  1842.             fprintf(stderr, "%s: ", ifname);
  1843.     fprintf(stderr, " -- not a regular file: unchanged");
  1844.     exit_stat = 1;
  1845.     } else if (statbuf.st_nlink > 1) {
  1846.     if(quiet)
  1847.             fprintf(stderr, "%s: ", ifname);
  1848.     fprintf(stderr, " -- has %d other links: unchanged",
  1849.         statbuf.st_nlink - 1);
  1850.     exit_stat = 1;
  1851.     } else if (exit_stat == 2 && (!force)) { /* No compression: remove file.Z */
  1852.     if(!quiet)
  1853.         fprintf(stderr, " -- file unchanged");
  1854.     } else {            /* ***** Successful Compression ***** */
  1855.     exit_stat = 0;
  1856.     mode = statbuf.st_mode & 07777;
  1857.     if (chmod(ofname, mode))        /* Copy modes */
  1858.         perror(ofname);
  1859.     chown(ofname, statbuf.st_uid, statbuf.st_gid);    /* Copy ownership */
  1860.     timep[0] = statbuf.st_atime;
  1861.     timep[1] = statbuf.st_mtime;
  1862.     utime(ofname, timep);    /* Update last accessed and modified times */
  1863.     if (unlink(ifname))    /* Remove input file */
  1864.         perror(ifname);
  1865.     if(!quiet)
  1866.         fprintf(stderr, " -- replaced with %s", ofname);
  1867.     return;        /* Successful return */
  1868.     }
  1869.  
  1870.     /* Unsuccessful return -- one of the tests failed */
  1871.     if (unlink(ofname))
  1872.     perror(ofname);
  1873. }
  1874. /*
  1875.  * This routine returns 1 if we are running in the foreground and stderr
  1876.  * is a tty.
  1877.  */
  1878. foreground()
  1879. {
  1880.     if(bgnd_flag) {    /* background? */
  1881.         return(0);
  1882.     } else {            /* foreground */
  1883.         if(isatty(2)) {        /* and stderr is a tty */
  1884.             return(1);
  1885.         } else {
  1886.             return(0);
  1887.         }
  1888.     }
  1889. }
  1890.  
  1891. onintr ( )
  1892. {
  1893.     if (!zcat_flg)
  1894.     unlink ( ofname );
  1895.     exit ( 1 );
  1896. }
  1897.  
  1898. oops ( )    /* wild pointer -- assume bad input */
  1899. {
  1900.     if ( do_decomp == 1 ) 
  1901.         fprintf ( stderr, "uncompress: corrupt input\n" );
  1902.     unlink ( ofname );
  1903.     exit ( 1 );
  1904. }
  1905.  
  1906. cl_block ()        /* table clear for block compress */
  1907. {
  1908.     register long int rat;
  1909.  
  1910.     checkpoint = in_count + CHECK_GAP;
  1911. #ifdef DEBUG
  1912.     if ( debug ) {
  1913.             fprintf ( stderr, "count: %ld, ratio: ", in_count );
  1914.              prratio ( stderr, in_count, bytes_out );
  1915.         fprintf ( stderr, "\n");
  1916.     }
  1917. #endif /* DEBUG */
  1918.  
  1919.     if(in_count > 0x007fffff) {    /* shift will overflow */
  1920.     rat = bytes_out >> 8;
  1921.     if(rat == 0) {        /* Don't divide by zero */
  1922.         rat = 0x7fffffff;
  1923.     } else {
  1924.         rat = in_count / rat;
  1925.     }
  1926.     } else {
  1927.     rat = (in_count << 8) / bytes_out;    /* 8 fractional bits */
  1928.     }
  1929.     if ( rat > ratio ) {
  1930.     ratio = rat;
  1931.     } else {
  1932.     ratio = 0;
  1933. #ifdef DEBUG
  1934.     if(verbose)
  1935.         dump_tab();    /* dump string table */
  1936. #endif
  1937.      cl_hash ( (count_int) hsize );
  1938.     free_ent = FIRST;
  1939.     clear_flg = 1;
  1940.     output ( (code_int) CLEAR );
  1941. #ifdef DEBUG
  1942.     if(debug)
  1943.             fprintf ( stderr, "clear\n" );
  1944. #endif /* DEBUG */
  1945.     }
  1946. }
  1947.  
  1948. cl_hash(hsize)        /* reset code table */
  1949.     register count_int hsize;
  1950. {
  1951. #ifndef XENIX_16    /* Normal machine */
  1952.     register count_int *htab_p = htab+hsize;
  1953. #else
  1954.     register j;
  1955.     register long k = hsize;
  1956.     register count_int *htab_p;
  1957. #endif
  1958.     register long i;
  1959.     register long m1 = -1;
  1960.  
  1961. #ifdef XENIX_16
  1962.     for(j=0; j<=8 && k>=0; j++,k-=8192) {
  1963.     i = 8192;
  1964.     if(k < 8192) {
  1965.         i = k;
  1966.     }
  1967.     htab_p = &(htab[j][i]);
  1968.     i -= 16;
  1969.     if(i > 0) {
  1970. #else
  1971.     i = hsize - 16;
  1972. #endif
  1973.      do {                /* might use Sys V memset(3) here */
  1974.         *(htab_p-16) = m1;
  1975.         *(htab_p-15) = m1;
  1976.         *(htab_p-14) = m1;
  1977.         *(htab_p-13) = m1;
  1978.         *(htab_p-12) = m1;
  1979.         *(htab_p-11) = m1;
  1980.         *(htab_p-10) = m1;
  1981.         *(htab_p-9) = m1;
  1982.         *(htab_p-8) = m1;
  1983.         *(htab_p-7) = m1;
  1984.         *(htab_p-6) = m1;
  1985.         *(htab_p-5) = m1;
  1986.         *(htab_p-4) = m1;
  1987.         *(htab_p-3) = m1;
  1988.         *(htab_p-2) = m1;
  1989.         *(htab_p-1) = m1;
  1990.         htab_p -= 16;
  1991.     } while ((i -= 16) >= 0);
  1992. #ifdef XENIX_16
  1993.     }
  1994.     }
  1995. #endif
  1996.         for ( i += 16; i > 0; i-- )
  1997.         *--htab_p = m1;
  1998. }
  1999.  
  2000. prratio(stream, num, den)
  2001. FILE *stream;
  2002. long int num, den;
  2003. {
  2004.     register int q;            /* Doesn't need to be long */
  2005.  
  2006.     if(num > 214748L) {        /* 2147483647/10000 */
  2007.         q = num / (den / 10000L);
  2008.     } else {
  2009.         q = 10000L * num / den;        /* Long calculations, though */
  2010.     }
  2011.     if (q < 0) {
  2012.         putc('-', stream);
  2013.         q = -q;
  2014.     }
  2015.     fprintf(stream, "%d.%02d%%", q / 100, q % 100);
  2016. }
  2017.  
  2018. version()
  2019. {
  2020.     fprintf(stderr, "%s, Berkeley 5.7 9/17/85\n", rcs_ident);
  2021.     fprintf(stderr, "Options: ");
  2022. #ifdef vax
  2023.     fprintf(stderr, "vax, ");
  2024. #endif
  2025. #ifdef NO_UCHAR
  2026.     fprintf(stderr, "NO_UCHAR, ");
  2027. #endif
  2028. #ifdef SIGNED_COMPARE_SLOW
  2029.     fprintf(stderr, "SIGNED_COMPARE_SLOW, ");
  2030. #endif
  2031. #ifdef XENIX_16
  2032.     fprintf(stderr, "XENIX_16, ");
  2033. #endif
  2034. #ifdef COMPATIBLE
  2035.     fprintf(stderr, "COMPATIBLE, ");
  2036. #endif
  2037. #ifdef DEBUG
  2038.     fprintf(stderr, "DEBUG, ");
  2039. #endif
  2040. #ifdef BSD4_2
  2041.     fprintf(stderr, "BSD4_2, ");
  2042. #endif
  2043.     fprintf(stderr, "BITS = %d\n", BITS);
  2044. }
  2045. AlBeRtEiNsTeIn
  2046. echo unbundling usermem.sh 1>&2
  2047. cat >usermem.sh <<'AlBeRtEiNsTeIn'
  2048. #!/bin/sh -
  2049. #
  2050. #    @(#)usermem.sh    5.4 (Berkeley) 9/17/85
  2051. #
  2052. : This shell script snoops around to find the maximum amount of available
  2053. : user memory.  These variables need to be set only if there is no
  2054. : /usr/adm/messages.  KMEM, UNIX, and CLICKSIZE can be set on the command
  2055. : line, if desired, e.g. UNIX=/unix
  2056. KMEM=/dev/kmem        # User needs read access to KMEM
  2057. UNIX=
  2058. # VAX            CLICKSIZE=512,    UNIX=/vmunix
  2059. # PDP-11        CLICKSIZE=64,    UNIX=/unix
  2060. # CADLINC 68000        CLICKSIZE=4096,    UNIX=/unix
  2061. # Perkin-Elmer 3205    CLICKSIZE=4096,    UNIX=/edition7
  2062. # Perkin-Elmer all others, CLICKSIZE=2048, UNIX=/edition7
  2063. CLICKSIZE=512
  2064. eval $*
  2065.  
  2066. if test -n "$UNIX"
  2067. then
  2068.     : User must have specified it already.
  2069. elif test -r /vmunix
  2070. then
  2071.     UNIX=/vmunix
  2072.     CLICKSIZE=512    # Probably VAX
  2073. elif test -r /edition7
  2074. then
  2075.     UNIX=/edition7
  2076.     CLICKSIZE=2048    # Perkin-Elmer: change to 4096 on a 3205
  2077. elif test -r /unix
  2078. then
  2079.     UNIX=/unix        # Could be anything
  2080. fi
  2081.  
  2082. SIZE=0
  2083. # messages: probably the most transportable
  2084. if test -r /usr/adm/messages -a -s /usr/adm/messages
  2085. then
  2086.     SIZE=`grep avail /usr/adm/messages | sed -n '$s/.*[     ]//p'`
  2087. fi
  2088.  
  2089. if test 0$SIZE -le 0        # no SIZE in /usr/adm/messages
  2090. then
  2091.     if test -r $KMEM        # Readable KMEM
  2092.     then
  2093.     if test -n "$UNIX"
  2094.     then
  2095.         SIZE=`echo maxmem/D | adb $UNIX $KMEM | sed -n '$s/.*[     ]//p'`
  2096.         if test 0$SIZE -le 0
  2097.         then
  2098.         SIZE=`echo physmem/D | adb $UNIX $KMEM | sed -n '$s/.*[     ]//p'`
  2099.         fi
  2100.         SIZE=`expr 0$SIZE '*' $CLICKSIZE`
  2101.     fi
  2102.     fi
  2103. fi
  2104.  
  2105. case $UNIX in
  2106.     /vmunix)        # Assume 4.2bsd: check for resource limits
  2107.     MAXSIZE=`csh -c limit | awk 'BEGIN    { MAXSIZE = 1000000 }
  2108. /datasize|memoryuse/ && NF == 3    { if ($2 < MAXSIZE) MAXSIZE = $2 }
  2109. END    { print MAXSIZE * 1000 }'`
  2110.     if test $MAXSIZE -lt $SIZE
  2111.     then
  2112.         SIZE=$MAXSIZE
  2113.     fi
  2114.     ;;
  2115. esac
  2116.  
  2117. if test 0$SIZE -le 0
  2118. then
  2119.     echo 0;exit 1
  2120. else
  2121.     echo $SIZE
  2122. fi
  2123. AlBeRtEiNsTeIn
  2124.